package tasks.zhuanyeji.npu最小峰值占用;


import java.util.Arrays;

public class Solution {

    /**
     * 计算NPU最小峰值占用
     *
     * @param loads 每个任务的计算负载数组
     * @param m     需要划分的批次数
     * @return 最小可能的峰值占用
     */
    public int minPeakLoad(int[] loads, int m) {
        // 边界情况检查
        if (loads == null || loads.length == 0 || m <= 0) {
            throw new IllegalArgumentException("输入参数无效");
        }

        if (m > loads.length) {
            throw new IllegalArgumentException("批次数不能大于任务数");
        }

        // 1. 确定二分查找的边界
        int left = 0;  // 下界：数组中的最大值
        int right = 0; // 上界：数组所有元素之和

        for (int load : loads) {
            left = Math.max(left, load); // 找出最大单个任务负载
            right += load;               // 计算总负载
        }

        // 2. 二分查找
        while (left < right) {
            int mid = left + (right - left) / 2;

            // 3. 贪心验证：检查是否可以用不超过m个批次完成，且每个批次不超过mid
            if (canSplit(loads, m, mid)) {
                right = mid; // 可行，尝试更小的值
            } else {
                left = mid + 1; // 不可行，需要增大mid
            }
        }

        return left;
    }

    /**
     * 贪心验证函数：检查是否可以将任务分成不超过m个批次，且每个批次总负载不超过maxLoad
     *
     * @param loads   任务负载数组
     * @param m       最大允许的批次数
     * @param maxLoad 每个批次允许的最大负载
     * @return 是否可行
     */
    private boolean canSplit(int[] loads, int m, int maxLoad) {
        int currentBatchLoad = 0; // 当前批次的累计负载
        int batchCount = 1;       // 已使用的批次数，至少有一个批次

        for (int load : loads) {
            // 如果当前任务无法加入当前批次（会超出maxLoad）
            if (currentBatchLoad + load > maxLoad) {
                // 开启新的批次
                batchCount++;
                currentBatchLoad = load;

                // 如果批次数已超过限制，返回不可行
                if (batchCount > m) {
                    return false;
                }
            } else {
                // 将当前任务加入当前批次
                currentBatchLoad += load;
            }
        }

        return true;
    }

    // 测试用例
    public static void main(String[] args) {
        Solution solution = new Solution();

        // 示例1
        int[] loads1 = {1, 2, 3, 4, 5};
        int m1 = 3;
        System.out.println("示例1 - 输入: " + Arrays.toString(loads1) + ", m = " + m1);
        System.out.println("输出: " + solution.minPeakLoad(loads1, m1)); // 期望输出: 6

        // 示例2
        int[] loads2 = {7, 2, 5, 10, 8};
        int m2 = 2;
        System.out.println("\n示例2 - 输入: " + Arrays.toString(loads2) + ", m = " + m2);
        System.out.println("输出: " + solution.minPeakLoad(loads2, m2)); // 期望输出: 18

        // 示例3
        int[] loads3 = {10, 5, 13, 4, 8, 7, 3};
        int m3 = 3;
        System.out.println("\n示例3 - 输入: " + Arrays.toString(loads3) + ", m = " + m3);
        System.out.println("输出: " + solution.minPeakLoad(loads3, m3)); // 期望输出: 17
        // 额外验证：手动验证17和18是否可行
        System.out.println("\n额外验证：");
        System.out.println("峰值占用17是否可行: " + solution.canSplit(loads3, m3, 17));
        System.out.println("峰值占用18是否可行: " + solution.canSplit(loads3, m3, 18));
    }
}
